//给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素
// 。
//
// 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1
//。
//
//
//
// 示例 1:
//
//
//输入: nums = [1,2,1]
//输出: [2,-1,2]
//解释: 第一个 1 的下一个更大的数是 2；
//数字 2 找不到下一个更大的数；
//第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
//
//
// 示例 2:
//
//
//输入: nums = [1,2,3,4,3]
//输出: [2,3,4,-1,4]
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 10⁴
// -10⁹ <= nums[i] <= 10⁹
//
//
// Related Topics 栈 数组与矩阵 单调栈 👍 794 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function nextGreaterElements(nums: number[]): number[] {

    //? 单调递减呗 还说啥呢
    let stack : number[] = []
    let res : number[] = new Array(nums.length).fill(-1)
    //? 由于是循环 所以重复一份
    let doubleNums = new Array(...nums, ...nums)
    stack.push(0)
    //? [1,2,3,4,3,1,2,3,4,3]
    //? [1,2,1,1,2,1]
    for (let i = 1; i < doubleNums.length; i ++) {
        while (stack.length > 0 && doubleNums[i] > nums[stack[stack.length - 1]]) {
            res[stack[stack.length - 1]] = doubleNums[i]
            stack.pop()
        }
        //? 只入栈一半 因为另一半只用比较而不用入栈
        if (i < nums.length) {
            stack.push(i)
        }
    }
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
